In the modern mobile computing environment the security of the execution environment and of the data stored on the mobile device is becoming ever more important.
A GSM handset typically stores a unique identifier (known as the IMEI). This identifier must be immutable once the handset has been produced. The challenge for handset makers is to achieve this and also to protect the integrity of all the executable software which accesses the IMEI. There is no point in having the IMEI stored securely if the software can be modified never to access the stored value but to use another one. The challenge is therefore to protect the integrity of this software.
One approach would be to store the software in a region of read-only memory (ROM) where its integrity is guaranteed. However in practice this solution is not viable. This is because of the increasing complexity of the software which means that it is increasingly necessary to provide mechanisms which allow this software to be updated to fix problems. This may be achieved either via a physical connection typically at a service centre or over the wireless network using an over the air update mechanism.
The effect of this is that the software components are stored in modifiable storage, usually based on flash technology (although other mechanisms can be used). The important point however is that the contents of such devices can be modified and it becomes necessary to check the integrity of software stored in such devices when the device is booted and ideally before each execution of critical areas of functionality.
A standard mechanism to perform integrity checks is based on the use of secure mapping algorithms which uniquely (or at least substantially uniquely) map the software to generate check data. Examples of such algorithms are the hashing algorithms SHA-1 (FIPS 180-2) or HMAC (FIPS 198) which generate outputs known as checksums. To calculate any of these checksums it is necessary to read the whole of the software which is to be checked into memory and perform a significant amount of computation on the values. On a mobile device with limited CPU power and battery life this is a significant burden which will only increase as the size of the software running on such devices increases. A worse problem is that the time taken for this validation can significantly increase the time taken to boot the device.
This problem of the requirement for significant computation, power and worst of all boot time affects all mobile devices which must implement secure operation including devices such as MP3 players. In many cases the security level is even higher when Digital Rights Management (DRM) software is in use and the content decryption mechanisms must be protected.
Flash devices such as those used in most mobile equipment store data within them in a non-volatile manner. This storage is then presented to the processor either as an area of virtual memory allowing full virtual memory access or via a device interface which also allows random access to the contents.
A. Murat Fiskiran, Ruby B. Lee, “Runtime Execution Monitoring (REM) to Detect and Prevent Malicious Code Execution,” iccd, pp. 452-457, 2004 IEEE International Conference on Computer Design (ICCD'04), 2004 (hereinafter referred to as “Fiskiran et al”) describes a Memory Hashing (MH) process in which a memory is structured as a tree with the program data placed at the leaves. Every node of the tree contains the hash of the nodes (or leaves) below it. At the root of the tree is a root hash which is permanently kept in secure memory. The integrity of an incoming data block is checked by recursively verifying its hash and all the hashes of its parent nodes, up to the root hash.